from typing import List


# 岛屿的数量
# LeetCode 200
class Island_Nums:
    def numIslands(self, grid: List[List[str]]) -> int:
        result = 0
        row = len(grid)
        col = len(grid[0])
        for r in range(row):
            for c in range(col):
                if grid[r][c] == '1':
                    self.dfs(grid, r, c)
                    result += 1
        return result

    def dfs(self, grid: List[List[str]], r, c):
        if not self.inArea(grid, r, c) or grid[r][c] == '0':
            return
        grid[r][c] = '0'
        self.dfs(grid, r-1, c)
        self.dfs(grid, r+1, c)
        self.dfs(grid, r, c-1)
        self.dfs(grid, r, c+1)

    def inArea(self, grid: List[List[str]], r, c) -> bool:
        row = len(grid)
        col = len(grid[0])
        return 0 <= r < row and 0 <= c < col


# 岛屿的最大面积
# LeetCode 695. Max Area of Island （Medium）
class Max_Area_island:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        result = 0
        row = len(grid)
        col = len(grid[0])
        for r in range(row):
            for c in range(col):
                if grid[r][c] == 1:
                    a = self.area(grid, r, c)
                    result = max(result, a)
        return result

    def area(self, grid: List[List[int]], r, c) -> int:
        if not self.inArea(grid, r, c):
            return 0
        if grid[r][c] != 1:
            return 0
        grid[r][c] = 2
        return 1 + self.area(grid, r-1, c) + self.area(grid, r+1, c) + \
               self.area(grid, r, c-1) + self.area(grid, r, c+1)

    def inArea(self, grid: List[List[int]], r, c) -> bool:
        row = len(grid)
        col = len(grid[0])
        return 0 <= r < row and 0 <= c < col


# 填海造陆问题
# LeetCode 827. Making A Large Island （Hard）
class Largest_Island:
    def largestIsland(self, grid: List[List[int]]) -> int:
        return 0


# 岛屿的周长
# LeetCode 463. Island Perimeter （Easy）
class Island_Perimeter:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        row = len(grid)
        col = len(grid[0])
        for r in range(row):
            for c in range(col):
                if grid[r][c] == 1:
                    # 题目限制只有一个岛屿，计算一个即可
                    return self.dfs(grid, r, c)

    def dfs(self, grid: List[List[int]], r, c) -> int:
        # 函数因为「坐标 (r, c) 超出网格范围」返回，对应一条黄色的边
        if not self.inArea(grid, r, c):
            return 1
        # 函数因为「当前格子是海洋格子」返回，对应一条蓝色的边
        if grid[r][c] == 0:
            return 1
        # 函数因为「当前格子是已遍历的陆地格子」返回，和周长没关系
        if grid[r][c] != 1:
            return 0
        grid[r][c] = 2
        return self.dfs(grid, r-1, c) + self.dfs(grid, r+1, c) + self.dfs(grid, r, c-1) + self.dfs(grid, r, c+1)

    # 判断坐标 (r, c) 是否在网格中
    def inArea(self, grid: List[List[int]], r, c) -> bool:
        row = len(grid)
        col = len(grid[0])
        return 0 <= r < row and 0 <= c < col


if __name__ == '__main__':
    t = [
     [0,0,1,0,0,0,0,1,0,0,0,0,0],
     [0,0,0,0,0,0,0,1,1,1,0,0,0],
     [0,1,1,0,1,0,0,0,0,0,0,0,0],
     [0,1,0,0,1,1,0,0,1,0,1,0,0],
     [0,1,0,0,1,1,0,0,1,1,1,0,0],
     [0,0,0,0,0,0,0,0,0,0,1,0,0],
     [0,0,0,0,0,0,0,1,1,1,0,0,0],
     [0,0,0,0,0,0,0,1,1,0,0,0,0]
    ]
    s = [
        ["1", "1", "1", "1", "0"],
        ["1", "1", "0", "1", "0"],
        ["1", "1", "0", "0", "0"],
        ["0", "0", "0", "0", "0"]
    ]
    x = Island_Nums()
    print(x.numIslands(s))
